package week_07;

import java.util.Arrays;

/**
 * 1000. 合并石头的最低成本
 * 有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
 * <p>
 * 每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。
 * <p>
 * 找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：stones = [3,2,4,1], K = 2
 * 输出：20
 * 解释：
 * 从 [3, 2, 4, 1] 开始。
 * 合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。
 * 合并 [4, 1]，成本为 5，剩下 [5, 5]。
 * 合并 [5, 5]，成本为 10，剩下 [10]。
 * 总成本 20，这是可能的最小值。
 * 示例 2：
 * <p>
 * 输入：stones = [3,2,4,1], K = 3
 * 输出：-1
 * 解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.
 * 示例 3：
 * <p>
 * 输入：stones = [3,5,1,2,6], K = 3
 * 输出：25
 * 解释：
 * 从 [3, 5, 1, 2, 6] 开始。
 * 合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。
 * 合并 [3, 8, 6]，成本为 17，剩下 [17]。
 * 总成本 25，这是可能的最小值。
 */
public class MergeStones_1000 {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;

        int[] sums = new int[n];
        sums[0] = stones[0];
        for (int i = 1; i < n; i++) sums[i] = sums[i - 1] + stones[i];
        int[][][] dp = new int[n + 1][n + 1][k + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                // dp[i][j][k]=1000000000;
                Arrays.fill(dp[i][j],1000000000 );
            }

            dp[i][i][1] = 0;
        }

        for (int len = 2; len <= n; len++) {
            for (int l = 0; l <= n - len; l++) {
                int r = l + len - 1;
                for (int i = 2; i <= k; i++) {
                    for (int p = l; p < r; p++) {
                        dp[l][r][i] = Math.min(dp[l][r][i], dp[l][p][ 1] + dp[p + 1][r][i-1]);
                    }
                }
                dp[l][r][1] = Math.min(dp[l][r][1], dp[l][r][k] + sums[r] - ((l == 0) ? 0 : sums[l - 1]));
            }

        }
        return dp[0][n - 1][1] >= 1000000000 ? -1 : dp[0][n - 1][1];
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 4, 1};
        MergeStones_1000 test = new MergeStones_1000();
        test.mergeStones(arr, 2);
    }
}
